/**
 * Created With IntelliJ IDEA
 * Description:牛客网：BM34 判断是不是二叉搜索树
 * <a href="https://www.nowcoder.com/practice/a69242b39baf45dea217815c7dedb52b?tpId=295&tqId=2288088&ru=/exam/oj&qru=/ta/format-top101/question-ranking&sourceUrl=%2Fexam%2Foj">...</a>
 * User: DELL
 * Data: 2022-12-27
 * Time: 21:53
 */

//思路：因为二叉搜索树的特征就是中序遍历为递增序列，因此我们可以按照中序遍历的过程，
//     同时引入一个变量pre来记录中序遍历过程中的前一个结点的val，之后按照中序遍
//     历的步骤依次进行递归遍历，同时验证当前结点的val是否中序遍历过程中前一个结
//     点的val即可。
import java.util.*;

class TreeNode {
     int val = 0;
     TreeNode left = null;
     TreeNode right = null;
    public TreeNode(int val) {
        this.val = val;
    }
 }

public class Solution {
    //记录中序遍历过程中的前序结点的val
    private int pre = Integer.MIN_VALUE;
    public boolean isValidBST (TreeNode root) {
        //判空处理
        if (root == null) {
            return true;
        }
        //判断左子树是否为二叉搜索树
        if (!isValidBST(root.left)) {
            return false;
        }
        //与中序遍历过程中的前一个结点的val比较
        if (root.val < pre) {
            return false;
        }
        //更新pre的值
        pre = root.val;
        //判断右子树是否为二叉搜索树
        return isValidBST(root.right);
    }
}